package leetcode.editor.cn;//数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
//
//
//
// 示例 1：
//
//
//输入：n = 3
//输出：["((()))","(()())","(())()","()(())","()()()"]
//
//
// 示例 2：
//
//
//输入：n = 1
//输出：["()"]
//
//
//
//
// 提示：
//
//
// 1 <= n <= 8
//
// Related Topics 字符串 动态规划 回溯
// 👍 2430 👎 0

import java.util.LinkedList;
import java.util.List;

/**
题目：括号生成
2022-03-09 22:23:01
*/
public class GenerateParentheses22{
    public static void main(String[] args) {
        Solution solution = new GenerateParentheses22().new Solution();
        // TO TEST
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        List<String> res = new LinkedList<>();
        public List<String> generateParenthesis(int n) {
            if (n == 0) return res;
            StringBuilder tack = new StringBuilder();
            backtrack(n, n, tack);
            return res;
        }

        void backtrack(int left, int right, StringBuilder tack){
            if (left>right) return;
            // 数量小于 0 肯定是不合法的
            if (left < 0 || right < 0) return;
            if (left==0 && right==0){
                res.add(tack.toString());
            }
            tack.append('(');
            backtrack(left-1,right,tack);
            tack.deleteCharAt(tack.length()-1);

            tack.append(')');
            backtrack(left,right-1,tack);
            tack.deleteCharAt(tack.length()-1);
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
